package com.atcumt.xiaoyuan;

import java.util.HashMap;
import java.util.Map;

/**
 * 请找到等于 K 的最长时间段(即:多包、丢包和正常之和等于 K 的最长连续子数组长度)。
 * 如果不存在任意 一个符合要求的时间段，则返回 0。
 *
 * 注意:
 * nums 数组的总和是一定在 32 位有符号整数范围之内的。
 *
 * 示例 1:
 * 输入: nums = [1, -1, 5, -2, 3], k = 3
 * 输出: 4
 * 解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
 *
 * 示例 2:
 * 输入: nums = [-2, -1, 2, 1], k = 1
 * 输出: 2
 * 解释: 子数组 [-1, 2] 和等于 1，且长度最长
 *
 * nums = [-1], k=8
 * nums = [-1,-1,1,1,1,2,2,2],k=4
 */
public class HJOD {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, -1, 5, -2, 3};

        int[] nums2 = new int[]{-1,-1,1,1,1,2,2,2};
        int k = 4;
        HJOD hjod = new HJOD();
        int res = hjod.maxSubArray(nums2, k);
        System.out.println(res);
    }

    private int maxSubArray(int[] nums, int k) {
        int sum = 0;
        int res = Integer.MIN_VALUE;
        Map<Integer, Integer> sumToIdx = new HashMap<>();
        sumToIdx.put(0, -1);
        for (int i = 0; i <= nums.length - 1; i++) {
            sum += nums[i];
            if (!sumToIdx.containsKey(sum)) {
                sumToIdx.put(sum, i);
            }
            if (sumToIdx.containsKey(sum - k)) {
                Integer index = sumToIdx.get(sum - k);
                res = Math.max(res, i - index);
            }
        }
        return res == Integer.MIN_VALUE ? 0 : res;

    }
}
